package top100

import "sort"

func groupAnagrams(strs []string) [][]string {
	var existMap = make(map[[26]int][]string)
	for i := 0; i < len(strs); i++ {
		var curStr = strs[i]
		var curSort [26]int
		for j := 0; j < len(curStr); j++ {
			curSort[curStr[j]-'a']++
		}
		existMap[curSort] = append(existMap[curSort], curStr)
	}
	var res [][]string
	for _, vals := range existMap {
		res = append(res, vals)
	}
	return res
}
func lengthOfLongestSubstring(s string) int {
	var winMap = make(map[byte]int)
	var max = 0
	var leftidx = 0
	for i := 0; i < len(s); i++ {
		if idx, ok := winMap[s[i]]; ok {
			if idx >= leftidx {
				leftidx = idx + 1
			}
		}
		winMap[s[i]] = i
		var curWin = i - leftidx + 1
		if curWin > max {
			max = curWin
		}
	}
	return max
}
func firstMissingPositive(nums []int) int {
	var max = len(nums) + 1
	for i := 0; i < len(nums); i++ {
		if nums[i] <= 0 {
			nums[i] = max
		}
	}
	for i := 0; i < len(nums); i++ {
		var idx = abs(nums[i])
		if idx >= 1 && idx <= len(nums) {
			nums[idx-1] = -abs(nums[idx-1])
		}
	}
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}
	return max
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

type ListNode struct {
	Val  int
	Next *ListNode
}
type Node1 struct {
	Val    int
	Next   *Node1
	Random *Node1
}

func copyRandomList(head *Node1) *Node1 {
	if head == nil {
		return nil
	}
	var cur = head
	for cur != nil {
		var next = cur.Next
		var copyNode = &Node1{
			Val: cur.Val,
		}
		cur.Next = copyNode
		copyNode.Next = next
		cur = next
	}
	cur = head
	for cur != nil {
		var random = cur.Random
		var next = cur.Next
		if random != nil {
			next.Random = random.Next
		}
		cur = cur.Next.Next
	}
	cur = head
	var copyHead = cur.Next
	var pre = copyHead
	for cur != nil {
		var copyNode = cur.Next
		cur.Next = copyNode.Next
		cur = cur.Next
		pre.Next = copyNode
		pre = pre.Next
		pre.Next = nil
	}
	return copyHead
}
func combinationSum(candidates []int, target int) [][]int {
	sort.Slice(candidates, func(i, j int) bool {
		return candidates[i] < candidates[j]
	})
	return [][]int{}
}

func solveNQueens(n int) [][]string {
	var res [][]string
	var trackBack func(curRow, n int, queensAt []int, colMap, sumMap, subMap map[int]bool)
	trackBack = func(curRow, n int, queensAt []int, colMap, sumMap, subMap map[int]bool) {
		if curRow == n {
			var board = generateBoard(queensAt)
			res = append(res, board)
			return
		}
		for i := 0; i < n; i++ {
			if colMap[i] || sumMap[curRow+i] || subMap[curRow-i] {
				continue
			}
			queensAt[curRow] = i
			colMap[i] = true
			sumMap[curRow+i] = true
			subMap[curRow-i] = true
			trackBack(curRow+1, n, queensAt, colMap, sumMap, subMap)
			queensAt[curRow] = -1
			colMap[i] = false
			sumMap[curRow+i] = false
			subMap[curRow-i] = false
		}
	}
	var queensAt = make([]int, n)
	for i := 0; i < n; i++ {
		queensAt[i] = -1
	}
	trackBack(0, n, queensAt, map[int]bool{}, map[int]bool{}, map[int]bool{})
	return res
}

func generateBoard(queensAt []int) []string {
	var size = len(queensAt)
	var res = make([]string, size)
	for i := 0; i < size; i++ {
		var curStr = make([]byte, size)
		for j := 0; j < size; j++ {
			curStr[j] = '.'
		}
		curStr[queensAt[i]] = 'Q'
		res[i] = string(curStr)
	}
	return res
}

func searchInsert(nums []int, target int) int {
	if target <= nums[0] {
		return 0
	}
	var size = len(nums)
	if target == nums[size-1] {
		return size - 1
	}
	if target > nums[size-1] {
		return size
	}
	var left = 0
	var right = size - 1
	for left < right {
		var mid = left + (right-left)/2
		if target == nums[mid] {
			return mid
		} else if target > nums[mid] {
			if mid == size-1 || target <= nums[mid+1] {
				return mid + 1
			}
			left = mid + 1
		} else {
			// target < nums[mid]
			if mid == 0 || target > nums[mid-1] {
				return mid
			}
			right = mid - 1
		}
	}
	return -1
}

func searchRange(nums []int, target int) []int {
	if len(nums) == 0 {
		return []int{-1, -1}
	}
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = left + (right-left)/2
		if nums[mid] > target {
			right = mid - 1
		} else if nums[mid] < target {
			left = mid + 1
		} else {
			// 找左边端点
			var curRight = mid
			var leftPointIdx int
			for left <= curRight {
				var tempMid = left + (curRight-left)/2
				if nums[tempMid] < target {
					left = tempMid + 1
				} else {
					if tempMid == 0 || nums[tempMid-1] < target {
						leftPointIdx = tempMid
						break
					}
					curRight = tempMid - 1
				}
			}
			// 找右边端点
			var curLeft = mid
			var rightPointIdx int
			for curLeft <= right {
				var tempMid = curLeft + (right-curLeft)/2
				if nums[tempMid] > target {
					right = tempMid - 1
				} else {
					if tempMid == len(nums)-1 || nums[tempMid+1] > target {
						rightPointIdx = tempMid
						break
					}
					curLeft = tempMid + 1
				}
			}
			return []int{leftPointIdx, rightPointIdx}
		}
	}
	return []int{-1, -1}
}

func search(nums []int, target int) int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = left + (right-left)/2
		if nums[mid] == target {
			return mid
		}
		if nums[left] <= nums[mid] {
			if target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if target <= nums[right] && target > nums[mid] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

/**
 * @description: 416.分割等和子集
 * @keyword:
 * @author: kami
 * @date 2024/4/6 15:05
 */
func canPartition(nums []int) bool {
	var sum = 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	if sum%2 == 1 {
		return false
	}
	var target = sum / 2
	var dp = make([]bool, target+1)
	dp[0] = true
	for i := 0; i < len(nums); i++ {
		var temp []int
		for j := 0; j <= target-nums[i]; j++ {
			if dp[j] {
				temp = append(temp, j+nums[i])
			}
		}
		for m := 0; m < len(temp); m++ {
			dp[temp[m]] = true
		}
		if dp[target] {
			return true
		}
	}
	return dp[target]
}
